public class 通配符匹配_递归版 {
    public boolean isMatch(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        return dfs(s,p,0,0);
    }

    // 递归
    private boolean dfs(char[] s, char[] p, int i, int j) {
        // i 到底了
        if (i == s.length) {
            // j 也到底了, 肯定是匹配成功了
            if (j == p.length) {
                return true;
            } else {
                // i 已经到底了, 但是 j 没有到底, j 位置必须是 * 才可以匹配空字符, 会怎么样交给后面告诉我
                return p[j] == '*' && dfs(s,p,i,j + 1);
            }
        } else if (j == p.length) {
            // i 没有到底, 当时 j 到底了, 肯定是匹配失败
            return false;
        } else {
            // 如果两个都没有到底
            // 1. 这个位置是 * 字符
            if (p[j] == '*') {
                // * 直接作为空字符串, 跳过 j 字符
                // * 和 i 位置的字符进行匹配, 跳过 i 字符
                return dfs(s,p,i,j + 1) || dfs(s,p,i + 1,j);
            } else {
                // 2. 不为 *
                // 想要匹配成功必须要两个相等或者有 ? 匹配任何字符, 会怎么样后面告诉我
                return (p[j] == '?' || p[j] == s[i]) && dfs(s,p,i + 1,j + 1);
            }
        }
    }


}
